package DP.背包.每样无限;

/**
 * 思路：
 *      纯汉 -> 因为要全部凑法 -> 所以 拿/不拿 只要 [zhenghao_curSum是tar即可]
 *
 *
 * 【关键】 base case 思想：
 *         // 前0个 正好0
 *               // 先弄好写的 正好0 -> 全不拿 -> 一种可能
 *               // 再弄 前0个 -> 除了sum=0有一种可能，其他都无可能
 *
 *
 * ? 用后序解更简单，这个只是练下dp题感
 *
 */
public class 零钱兑换II518_每样无限_所有凑法_dp {
    public int change(int amount, int[] coins) {
        int n = coins.length;
        int[][] dp = new int[n+1][amount+1];

        // 正好0 -> 全不拿 -> 一种可能
        for(int i=0; i<dp.length ; i++)
            dp[i][0] = 1;
        // 前0个 -> 除了sum=0有一种可能，其他都无可能
        for(int i=1; i<dp[0].length ; i++)
            dp[0][i] = 0;

        for (int pN = 1; pN <= coins.length; pN++) {
            for (int now_cS = 1; now_cS <= amount; now_cS++) {

                int cI = pN - 1;
                if(now_cS - coins[cI] >= 0){
                    // 无限个 -> 拿后, 选择范围 不缩
                    int na = dp[pN][now_cS-coins[cI]] ;
                    // [很好想的] 就任性 就不拿
                    int buna = dp[pN-1][now_cS];
                    dp[pN][now_cS] = na+buna;
                }
                // [很好想的] 拿了就超了! -> 肯定不能拿
                else {
                    int buna = dp[pN-1][now_cS];
                    dp[pN][now_cS] = buna;
                }
            }
        }
        return dp[coins.length][amount];
    }
}
